package com.sicheng.蓝桥.练习题.基础数论;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/30 16:57
 */
public class 预处理所有的数的约数 {
    static int N = (int) 1e4;
    static ArrayList<Integer>[] list = new ArrayList[N + 1];

    // 复杂度 O(NlogN)
    static {
        Arrays.setAll(list, k -> new ArrayList<>(150));
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
                list[j].add(i); // i 是 j 的因子
            }
        }
    }

    public static void main(String[] args) {
        int max = 0;
        for (ArrayList<Integer> x : list) {
            max = Math.max(x.size(), max);
        }
        System.out.println(max);
    }
}
